1. Field of the Invention
This invention pertains to the field of non-recursive digital filters used for digital signal processing and real time digital video processing. In particular it pertains to an architectural realization, in the form of very large scale integrated (VLSI) circuits, of finite impulse response (FIR) filters which do not require multipliers and which have only coefficients of two to the Nth power.
2. Description of the Prior Art
Among the different types of digital filters there has been a great deal of interest in finite impulse response (FIR) digital filters (also called traversal filter). The reason for this is that powerful and mature optimization theories exist to aid in the filter design. FIR filters can easily be designed to approximate a prescribed magnitude/frequency response to arbitrary accuracy with an exactly linear phase characteristic. The non-recursive FIR filters contain only zeroes in the finite z-plane and hence are always stable. These features make them very attractive for most digital signal processing applications.
Finite impulse response (FIR) digital filters are widely used in digital signal processing, as well as in real-time digital video processing. The conventional hardware realization of an FIR digital filter utilizes the basic functional components of delay units, multipliers and adders. Among these basic functional components, multipliers are generally the most complex for hardware realization, and occupy large "real estate" area, which increases the cost of the filter. The cost of multipliers in discrete component systems is high. From the point of view of VLSI chip design, the area occupied by a multiplier on an IC filter chip is too large. Cost is not the only important factor; but the operational speed of a filter is even more significant in a variety of applications; for example, in real-time video processing and other high speed digital signal processing. In the conventional FIR digital filter, a high percentage of the propagation delay time is due to multipliers, which reduce the speed of the filter. Therefore, to improve the operational speed, reduce the cost and simplify the structural complexity for VLSI chip design, it is desirable to eliminate time-consuming multipliers from digital FIR filters.
Current technical literature includes numerous articles directed toward the reduction or elimination of multipliers in the architecture or design of FIR digital filters, while at the same time proposing solutions directed to increasing the speed of these filters for use in real time digital signal processing applications.
In the prior patent art, U.S. Pat. No. 3,979,701 discloses a non-recursive digital filter composed of a cascaded plurality of basic sections, each of which is characterized by coefficient values of integer powers of two's. The filter of this patent uses no multipliers and claims an operating speed several times faster than other filters which utilize multipliers.
The multiplierless FIR filter disclosed in this application has certain concepts which appear to be similar to those of U.S. Pat. No. 3,979,701 but there are important differences.
The filter described in U.S. Pat. No. 3,979,701 has two basic building blocks from which the filter is constructed: Type 1 and Type 2. The Type 1 unit has only coefficients with a value of 1 (see line 53 to line 56 of column 3 of U.S. Pat. No. 3,979,701); the Type 2 unit has only an even number of delay elements and only three coefficients, the center coefficient value of which is always equal to 1 (see line 7 to line 12 of column 4 of U.S. Pat. No. 3,979,701).